记一次Rust技术面试
256 人赞同了该文章
开场
虽然不是第一场面Rust，但却是我第一场需要写代码的Rust面试，难免有点紧张。
开场的时候，面试官说，中途他可能会作一些记录，所以可能会有一些停顿。我心想这个面试官大概是新手吧。后来整场面下来确实就如标准的流水线一样，一步一环节进行下去。
开场是常规的自我介绍。然后是面试官提问。可能是项目经历不太相关，面试官也没怎么提问我的项目，就直接进入题目考察阶段。
数据库索引考察
由于我项目经历中提到了数据库，于是面试官就顺手考了我一道数据库，应该算比较简单。我大致回忆题目如下：
已知订单有三种属性：订单ID、订单日期（精确到天）、订单完成状态（完成、未完成）。请设计出表示订单的数据库表，为其指定主键，并为以下查询建立索引：
1. 查找某一ID的订单内容；
2. 查找近一周的所有订单；
3. 查找所有未完成的订单；
4. 查找近一个月内所有已完成的订单。
我不太熟悉数据库索引，所以就随便答了个暴力方法：共ID、订单日期、订单完成状态三个字段，ID为主键，建四个索引：
- ID为索引；
- 日期为索引；
- 订单完成状态为索引；
- 日期+完成状态为索引。
非常简单粗暴。当然事后我才想起ID已经是主键不需要索引了。
这一题暴露了我对数据库索引几乎一无所知。
Rust算法题
面试官停顿了十几秒，记录完情况后，就开始下一题。他二话不说，在题目面板上写下这么三行：
Input a: 1->2->3->4
Input b: 2->3->4
Output: 1->4->6->8
他刚写完，正要叙述题目，我说我见过这题，就是右对齐相加吧。（事实上确实前几天在知乎上还看到过。）
本来一想到要写 链表 ，我就想还是用C++写算了，于是问面试官，有限定语言吗？他说，用Rust。
好的，这下打消了我用C++写的念头，开始用Rust编码。第一步先定义接口：
type NodePtr<T> = Option<Box<Node<T>>>;
struct Node<T> {
data: T,
next: NodePtr<T>,
}
fn add<T>(a: NodePtr<T>, b: NodePtr<T>) -> NodePtr<T> {
todo!()
}
我想到的算法很简单，先遍历一遍求出a和b的长度，然后跳过开头长度不一致的节点，把公共部分相加即可。复杂度 O(m + n)。
这时我突然想偷个懒，就问面试官，输出的结果要求复用输入链表的结构吗？面试官说最好复用，如果实在复用不了也能接受。于是我想那还是复用吧。
首先可以考虑几种特殊情况直接处理，即 a 、 b 有一个或两个为空的情况。剩下 a 与 b 都不为空的情况则是主要逻辑：
fn add<T>(a: NodePtr<T>, b: NodePtr<T>) -> NodePtr<T> {
match (a, b) {
(Some(a), Some(b)) => {
todo!()
}
(Some(a), None) | (None, Some(a)) => Some(a),
(None, None) => None,
}
}
大概花了十分钟编码，五分钟与编译器作斗争后，终于把面试官给的测试用例过了。
代码有点长，我直接贴Playground吧：
写完之后，面试官就开始读我的代码。他说写得还不错，考虑到了封装。然后问我，算法的效率是不是可再提高一下？
我突然一紧张，开始回想是不是哪里写的效率低了。我想到了求长度的函数 len ， 它是一个递归的写法，于是就说，这个 len 是图方便就写成了递归形式，这个也可以改成循环。然后下一个想到的点是，我分别对 a 、 b 两个链表作了两次遍历，这里也许可以再优化下？
再仔细一想，不对啊，这个时间复杂度已经是 O(m + n) 了啊，不可能比这更优啊？我也向面试官表达了这个想法，并更詳细地向面试官讲解了我的思路。
后来知道是面试官把我写的 into_vec 和 from_vec 也当作是算法逻辑中的一部分了。我于是向面试官解释：这是方便链表的构造和测试用的，按理说应该要实现 FromIterator 和 IntoIterator ，但这里为了快速实现就用了 Vec 作中转。这下面试官终于看完了我的代码。
按下来，面试官问我会用什么样的数据来测试，我就说，会测试其中一个为空、其中两个为空的情况，其他情况应该不用测试。面试官说，那具体写一下测试代码吧。
我简单写了几组，觉得应该差不多了。
fn test_add(a: Vec<i32>, b: Vec<i32>, expected: Vec<i32>) {
let a = Node::from_vec(a);
let b = Node::from_vec(b);
assert_eq!(into_vec(add(a, b)), expected);
}
fn main() {
test_add(vec![1, 2, 3, 4], vec![2, 3, 4], vec![1, 4, 6, 8]);
test_add(vec![], vec![2, 3, 4], vec![2, 3, 4]);
test_add(vec![1, 2, 3, 4], vec![], vec![1, 2, 3, 4]);
test_add(vec![1], vec![], vec![1]);
test_add(vec![], vec![-1], vec![-1]);
test_add(vec![0, 0, 1, 0], vec![0], vec![0, 0, 1, 0]);
}
这时面试官突然问我，如果输入是 [9, 9, 9, 9] 和 [1] 呢？我恍然大悟，原来这个加法是要 进位 的！看来我虽然前几天看到过这题，但只记住了一半的条件，想当然地认为直接是逐个节点相加了。
后来在LeetCode上找到了这道题，并重写了这个算法。
我的思路是：先反转两个链表，按从头对齐的方式相加后，再将链表反转回来并输出。这样的时间复杂度是 O(m + n) ，两个链表各需遍历两次。
Playground：
Rust基础考察
最后因为剩的时间不多了，面试官就问了几个比较基础的Rust问题。没有背过面试题，我也只是想到哪说到哪。
说一下Rust中的 智能指针
Rust中的智能指针有三个， Box<T> 、 Rc<T> 、 Arc<T> 。其中 ：
Box<T>是唯一所有权的指针，无额外开销。Rc<T>是线程不安全的共享所有权的指针，由引用计数实现；配套的Weak<T>不具有所有权， 只用来跟踪该指针指向的资源是否已被销毁。Arc<T>是线程安全的共享所有权的指针，其用法与Rc<T>基本相同。
说一下Rust中的
Cell
Cell<T> 提供了一种内部可变的机制。可以通过 &self 修改内部的值，而无需通过 &mut self 。它是零开销的，但它的修改只能整体地修改，不能通过 &self 拿到内部的 &mut T 。
另一种 RefCell<T> 则可以用 borrow 或 borrow_mut 通过 &self 拿到内部的 &mut T 。但它是有运行时开销的，内部会记录当前的借用状态，是未被借用，还是被可变借用，还是被不可变借用，以及被不可变借用了多少次。
解释一下Rust中
Deref、Drop、Clone、Copy、Any这几个trait。
Deref是解引用语义，结合Rust中的自动解引用机制，可允许自定义包装类型如智能指针等变量像内部变量一样使用，但使用仅限于取&self，如果要取&mut self则需要DerefMut这个trait。Drop即析构函数。在变量生命周期结束时将自动执行drop以销毁。Clone是复制语义，可由用户实现，表示复制一个对象。任何可复制的类都可以实现这个trait。Copy也是复制语义，但与Clone不同的是，它只是一个标记，用来告诉编译器，该类型可以直接通过memcpy复制，而无需其他动作。Copy通常用于原生类型及其组合类型（结构体、元组、枚举等）。Any提供了一种简单的动态反射机制，要求类型必须具有'static的生命周期。在运行时可以downcast到任意类型，但若实际类型与要转换的类型不一致时，将返回Err。
问到这里，面试就结束了，等了面试官二三十秒的时间作记录后，面试官也没有留提问的机会，就正式结束了。可能因为是一面的缘故吧，就纯考察一下基础，没有其他任何多余的信息。
本来以为Rust这样的语言不太会问链表题，结果还是问到了，看来链表确实属于高频考题。不过能想到的是，除非专门想考察 unsafe 的内容，应该不会涉及双向链表。面试时如果用Rust写双向链表，感觉是纯属找不痛快啊。
第二天接到通知，一面已经过了，并预约了二面。如果二面能遇到一些有意思的题目，我会继续更新此文。
最后想吐槽一下牛客的面试界面。总体来讲功能挺到位，有代码窗口并且有简单的代码提示功能、也可运行，有白板演示功能，有文件上传功能，有屛幕共享功能，考虑周到。但有一点令我没想到的是，虽然代码编辑窗口提供了vim键位，但在我敲 S 键的时候，整个页面全部卡住，除了视频画面和音频还能用以外，其余的功能全部失效。导致我整场代码敲下来三次重新进了面试房间，体验不太好。后来是开了IDE，屛幕共享给面试官写的代码。
但这样也好，开了IDE后，写Rust的效率大幅提升，至少在我看到IDE给的波浪线提示之后就能把一些语法错误改掉，而不必等到执行时再照着编译错误一个个改。
这样看来，写Rust还真离不开IDE的提示与检查，不然像 Option<Box<Node<T>>> 这样嵌套层次多的类型，稍不注意就会少一个 unwrap 、 as_ref 、 as_deref 之类的。
编辑于 2021-09-19 13:45大学没怎么学，此法自学Java7个月，可以找到12K左右的工作
[
我是一个二本院校，专业是机械工程，当时以为考上了大学就可以高枕无忧放开了玩，可以说我整个大学期间都是打游戏过来的。到了大四才发现，同学们都陆续去找了实习，有的做机械工作，...